package oleg.util;

public class Arrays
{
  /**
   * Tuning parameter: list size at or below which insertion sort will be
   * used in preference to mergesort or quicksort.
   */
  private static final int INSERTIONSORT_THRESHOLD = 7;

  public static void sort(String[] a) {
    String aux[] = new String[a.length];
    System.arraycopy(a, 0, aux, 0, a.length);
    mergeSort(aux, a, 0, a.length, 0);
  }

  private static void mergeSort(String src[], String dest[],
                                int low, int high, int off) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
      for (int i=low; i<high; i++)
        for (int j=i; j>low &&
               dest[j-1].compareTo(dest[j])>0; j--)
          swap(dest, j, j-1);
      return;
    }

    // Recursively sort halves of dest into src
    int destLow  = low;
    int destHigh = high;
    low  += off;
    high += off;
    int mid = (low + high) >> 1;
    mergeSort(dest, src, low, mid, -off);
    mergeSort(dest, src, mid, high, -off);

    // If list is already sorted, just copy from src to dest.  This is an
    // optimization that results in faster sorts for nearly ordered lists.
    if (src[mid-1].compareTo(src[mid]) <= 0) {
      System.arraycopy(src, low, dest, destLow, length);
      return;
    }

    // Merge sorted halves (now in src) into dest
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
      if (q >= high || p < mid && src[p].compareTo(src[q])<=0)
        dest[i] = src[p++];
      else
        dest[i] = src[q++];
    }
  }

  private static void swap(Object x[], int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
  } 

  public static int binarySearchString(String[] a, String key) {
    int low = 0;
    int high = a.length-1;

    while (low <= high) {
	    int mid = (low + high) >> 1;
	    String midVal = a[mid];
	    int cmp = midVal.compareTo(key);

	    if (cmp < 0)
        low = mid + 1;
	    else if (cmp > 0)
        high = mid - 1;
	    else
        return mid; // key found
    }
    return -(low + 1);  // key not found.
  }
}